/*
 * @lc app=leetcode.cn id=934 lang=typescript
 *
 * [934] 最短的桥
 */

// @lc code=start
function shortestBridge(grid: number[][]): number {
  const n = grid.length;
  const dirs = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  // 岛屿坐标
  const islands: number[][] = [];
  // 队列,BFS
  const queue: number[][] = [];
  // 遍历每个单元，将访问过的岛屿记作-1
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 不是岛屿或者已访问过
      if (grid[i][j] !== 1) continue;
      queue.push([i, j]);
      // 标记访问过
      grid[i][j] = -1;
      // bfs岛屿
      while (queue.length) {
        const island = queue.shift()!;
        islands.push(island);
        //遍历四周
        for (const [x, y] of dirs) {
          const nx = island[0] + x;
          const ny = island[1] + y;
          if (nx < 0 || nx >= n) continue;
          if (ny < 0 || ny >= n) continue;
          if (grid[nx][ny] !== 1) continue;
          queue.push([nx, ny]);
          grid[nx][ny] = -1;
        }
      }

      // 利用第一个找到的岛屿 bfs 寻找另一个岛屿
      for (const island of islands) {
        queue.push(island);
      }

      let step = 0;
      while (queue.length) {
        const sz = queue.length;
        for (let k = 0; k < sz; k++) {
          const island = queue.shift()!;
          for (const [x, y] of dirs) {
            const nx = island[0] + x;
            const ny = island[1] + y;
            if (nx < 0 || nx >= n) continue;
            if (ny < 0 || ny >= n) continue;
            if (grid[nx][ny] === -1) continue;
            if (grid[nx][ny] === 0) {
              queue.push([nx, ny]);
              grid[nx][ny] = -1;
            } else if (grid[nx][ny] === 1) {
              return step;
            }
          }
        }
        step++;
      }
    }
  }
  return 0;
}
// @lc code=end
